package algorithmTopics.heap;

/**
 * 最大堆
 *
 * @author 86155
 * @date 2025/05/24
 */
public class MaxHeap {

    int[] array;
    int size;

    public MaxHeap(int capacity) {
        this.array = new int[capacity];
    }

    public MaxHeap(int[] array) {
        this.array = array;
        this.size = array.length;
        heapify();
    }

    /**
     * 向堆添加元素
     *
     * @param offered 提供
     * @return boolean
     * 成功返回true
     */
    public boolean offer( int offered) {
        if (this.size == this.array.length) {
            //说明大小满了
            return false;
        }
        //执行上浮
        up(offered);
        return true;
    }

    private void up(int offered) {
        //当前的位置
        int child = size;
        //父元素的位置
        int parent = (child - 1) / 2;
        //上浮到顶
        while (child > 0) {
            if (this.array[parent] < offered) {
                this.array[child] = this.array[parent];
            } else {
                break;
            }
            child = parent;
        }
        //赋值
        this.array[child] = offered;
    }

    /**
     * 建堆
     * 1.找到最后一个非叶子节点
     * 2.从后向前下潜
     */
    private void heapify() {
        // 非叶子节点定位公式
        int index = size / 2 - 1;
        for (int i = index; i >=0 ; i--) {
            dive(i);
        }

    }


    /**
     * 获取堆顶元素
     *
     * @return int
     */
    public int peek() {
        return array[0];
    }

    /**
     * 下潜
     * :把子节点 较大的和当前节点进行交换
     * @param parent 父节点索引
     */
    private void dive(int parent) {
        //定位左右节点 索引
        int left = parent * 2 + 1;
        int right = left + 1;
        int maxIndex = parent;
        //分别进行比较
        if (left < size && array[maxIndex] < array[left]) {
            maxIndex = left;
        }
        if (right < size && array[maxIndex] < array[right]) {
            maxIndex = right;
        }
        //判断是不是改变, 改变了就需要继续下潜
        if (parent != maxIndex) {
            swap(maxIndex,parent);
            dive(maxIndex);
        }
    }

    /**
     * 交换
     *
     * @param maxIndex 最大索引
     * @param parent   父节点索引
     */
    private void swap(int maxIndex, int parent) {
        int temp = array[maxIndex];
        array[maxIndex] = array[parent];
        array[parent] = temp;
    }

    /**
     * 删除堆顶元素
     *
     */
    public int poll() {
        // 把堆顶元素记录
        int top = array[0];
        //再与最后一个交换
        swap(0,size-1);
        //最后大小减少
        size--;
        //重新排序下潜
        dive(0);
        return top;
    }

    /**
     * 删除指定位置的堆元素
     *
     * @return int
     */
    public int poll(int index) {
        //记录要删除位置的元素
        int yuan = array[index];
        swap(index,size - 1);
        size--;
        dive(index);
        return yuan;
    }

    /**
     * 更换堆顶元素
     *
     * @param a a
     */
    public void replace(int a) {
        this.array[0] = a;
        dive(0);
    }
}
